package 每日一题;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-22
 **/

public class No318最大单词长度乘积 {

    /**
     * 给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，
     * 并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
     * <p>
     * 示例 1:
     * 输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
     * 输出: 16
     * 解释: 这两个单词为 "abcw", "xtfn"。
     * 示例 2:
     * 输入: ["a","ab","abc","d","cd","bcd","abcd"]
     * 输出: 4
     * 解释: 这两个单词为 "ab", "cd"。
     * 示例 3:
     * 输入: ["a","aa","aaa","aaaa"]
     * 输出: 0
     * 解释: 不存在这样的两个单词。
     *  
     * 提示：
     * 2 <= words.length <= 1000
     * 1 <= words[i].length <= 1000
     * words[i] 仅包含小写字母
     */

    /**
     * 1. 平庸解法很容易想到,给每个字符单独分配一个set,然后遍历所有字符,每个字符再遍历其他字符的set,
     * 如果都没有相交,那么它们两者就可以进行相乘。 空间复杂度过高。
     * 2. 我们可以将一个字符串转成一个int型数字,int型总共32位,每一位可以代表一个字符,小写字母26个,
     * 所有一个int型完全可以表明某个字符是否出现在当前字符串当中。
     */
    public int maxProduct(String[] words) {

        int[] arr = new int[words.length];

        for (int i = 0; i < words.length; i++) {
            char[] chars = words[i].toCharArray();
            for (char c : chars) {
                int cIndex = c - 'a';
                arr[i] |= 1 << cIndex;
            }
        }

        int result = 0;

        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((arr[i] & arr[j]) == 0) {
                    result = Math.max(result, words[i].length() * words[j].length());
                }
            }
        }

        return result;
    }

}
